import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * Created With IntelliJ IDEA
 * Description:leetcode：面试题 17.14. 最小K个数
 * <a href="https://leetcode.cn/problems/smallest-k-lcci/">...</a>
 * User: DELL
 * Data: 2023-01-23
 * Time: 23:53
 */

public class Solution {
    //数据范围
    //0 <= len(arr) <= 100000
    //0 <= k <= min(100000, len(arr))
    public int[] smallestK(int[] arr, int k) {
        int[] ret = new int[k];
        if (k == 0) {
            return ret;
        }
        //大根堆
        PriorityQueue<Integer> heap = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - 01;
            }
        });
        //前K个元素入堆
        for (int i = 0; i < k; i++) {
            heap.offer(arr[i]);
        }
        //剩余元素与堆头元素比较
        for (int i = k; i < arr.length; i++) {
            if (arr[i] < heap.peek()) {
                heap.poll();
                heap.offer(arr[i]);
            }
        }
        //返回堆中元素
        for (int i = 0; i < k; i++) {
            ret[i] = heap.poll();
        }
        return ret;
    }
}